#pragma once
#include <assert.h>
// 这节 简单讲了一下使用，然后大部分是模拟实现。
// 1. 有个地方要有合适的 构造函数
// 2.迭代器如何实现+1 如何自动跳到下一个节点的？

// ———————————————————————————————————————————————————以下部分为便于理解整体逻辑框架结构而写的
// 分为以下几大部分：
// 节点结构体模板、__list_iterator 结构体模板、list结构体模板（由一个个节点组成）、测试函数。
//
// ———————————————————————————————————————————————————以下部分为便于理解整体逻辑框架结构而写的
// 分为以下几大部分：
//	节点结构体模板
//	__list_iterator 结构体模板
//	list结构体模板（由一个个节点组成）
//	测试函数
// 首先，我们定义了一个节点结构体模板 ListNode，它包含：
//
//	ListNode* 类型的 _next 和 _prev 指针，分别指向前后节点。
//	T 类型的 _data，存放节点的数据。
//	ListNode 的构造函数初始化这些成员。
// 然后，我们定义了一个模板结构体 __list_iterator，用于实现链表的迭代器。这个迭代器包含：
//
//	一个指向当前节点的指针 _node。
//	构造函数、前置和后置 ++、-- 运算符重载、解引用运算符、相等和不相等比较运算符等操作。
// 为了简化代码，__list_iterator 使用了两个 typedef：
//	将 ListNode<T> 重命名为 Node。
//	将 __list_iterator<T, Ref, Ptr> 重命名为 self。
// 接下来，我们实现了 list 结构体模板。它包含一个带哨兵位的头结点 _head，类型为 Node* 。通过这个头结点以及迭代器指向的各个节点，形成一个带头的双向循环链表。
//
// 在 list 中，我们将 __list_iterator<T, T&, T*> 重命名为 iterator，将 __list_iterator<T, const T&, const T*> 重命名为 const_iterator，
// 一种是普通迭代器，一种是常量迭代器，以便用户更方便地使用迭代器。
//
// 通过这些定义，我们实现了一个功能完整的双向循环链表，并且提供了迭代器接口，使得用户可以方便地遍历和操作链表中的元素。
//
// 这个结构通过 ListNode 实现了双向节点连接，通过 __list_iterator 实现了链表的遍历和操作接口，并通过 list 结构体模板实现了整体的双向循环链表功能。测试函数用于验证各部分的功能和接口是否正常运行。
//

// 声明一个命名空间 mylist
namespace mylist
{

    // 定义一个模板结构体 ListNode，表示链表的节点
    template <class T> // 每个模板类或模板函数的定义都需要用 template<class T> 来声明。这样做的原因是为了告诉编译器这个类或函数是一个模板，且它是依赖于一个类型参数 T
    struct ListNode
    {

        // 构造函数，使用默认参数 T() 初始化 _data，并将 _next 和 _prev 初始化为 nullptr
        ListNode(const T &x = T())
            : _next(nullptr), _prev(nullptr) // 记得加上 ,
              ,
              _data(x)
        {
        }
        ListNode<T> *_next; /// 指向下一个节点的指针
        ListNode<T> *_prev; // 指向上一个节点的指针
        T _data;            // 节点存储的数据
    };
    // ListNode(const T& x = T())  必须加上 =T()  !!!
    // 默认参数的提供：
    //	构造函数中的 = T() 表示如果调用者在创建 ListNode 对象时没有提供参数 x，则会使用 T() 这个默认值来初始化 _data 成员变量。
    //	灵活性：
    //	这种构造函数提供了更大的灵活性。如果调用者提供了参数 x，则会使用提供的值来初始化节点的 _data 成员；如果没有提供参数 x，则会使用 T() 的默认构造函数生成一个默认值来初始化 _data。
    //	适用性：
    //	对于链表节点来说，可能存在需要默认构造的情况，例如默认构造一个空节点或者默认值为特定类型的情况。通过提供默认参数，可以简化在某些场景下节点的创建。

    // 结构体（struct）？？？
    //	是一种自定义数据类型，用于将多个相关的变量组合在一起。结构体可以包含基本数据类型、指针、引用、其他结构体、类等成员。与类（class）的主要区别在于结构体的默认访问控制是公有的（public），
    //	而类的默认访问控制是私有的（private）。
    // 带有构造函数的结构体：
    //	结构体可以包含构造函数，用于初始化成员变量。函数名就是结构体名

    // 为什么ListNode<T>* _prev; 要加<T>???
    //	模板类 ListNode 是一个通用类型，它可以被实例化为不同的数据类型。加上 <T> 是为了告诉编译器 _next 是一个指向相同类型的 ListNode 实例的指针。
    //	这里，ListNode 是一个模板类，它可以用任何类型的 T 来实例化。例如，你可以有一个 ListNode<int> 用于整数类型，或者一个 ListNode<double> 用于浮点数类型。
    //	ListNode<int>* intNode;
    //	ListNode<double>* doubleNode;
    // 在模板类的内部，也需要指定具体类型。例如，当定义 _next 指针时，需要明确它指向的是哪种类型的 ListNode，因此使用 ListNode<T>*。如果不加 <T>，编译器将不知道 _next 是指向哪个具体实例化类型的 ListNode。
    //	比如：
    //	ListNode<int> node;
    //	node._next = new ListNode<int>(5);  // 正确，_next 是指向 ListNode<int> 的指针

    //	ListNode<double> dnode;
    //	dnode._next = new ListNode<double>(3.14);  // 正确，_next 是指向 ListNode<double> 的指针

    // 定义一个模板结构体 __list_iterator，用于实现链表的迭代器
    template <class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef ListNode<T> Node;                  // 定义节点类型的别名
        typedef __list_iterator<T, Ref, Ptr> self; // 定义迭代器类型的别名
        //__list_iterator 被定义为一个模板结构体，并且引入了三个模板参数：T, Ref, 和 Ptr。通过不同的类型实例化 Ref 和 Ptr，我们可以区分出普通迭代器和常量迭代器。

        Node *_node; // 指向链表节点的指针

        // 构造函数，接受一个节点指针
        __list_iterator(Node *x)
            : _node(x)
        {
        }
        //__list_iterator 的构造函数接受一个指向 ListNode<T> 的指针 x，然后将 _node 成员变量初始化为 x。因此，每个 __list_iterator<T> 对象都包含一个指向 ListNode<T> 的指针 _node。
        // 另外：构造函数的名字必须与类的名字完全相同，不能使用类型的别名代替构造函数的名字。 上面self(Node* x)  是错的

        // 前置++运算符重载，使迭代器指向下一个节点。
        //++it
        self &operator++()
        {
            _node = _node->_next;
            return *this;
        }
        // 为什么返回引用
        // 这里的前置++运算符重载返回的是一个引用，即 self & 。它的作用是使迭代器向前移动到下一个节点，并返回移动后的迭代器对象自身。这种形式的重载通常在使用时会直接对迭代器进行修改，并返回修改后的对象的引用，以便支持链式操作。

        // 前置++运算符不需要任何参数，只需将迭代器移动到下一个位置并返回自身的引用即可。具体来说，它会将迭代器所指向的节点指针 _node 移动到下一个节点 _next，然后返回当前对象自身的引用 (*this)。

        // 后置++运算符重载，使迭代器指向下一个节点，并返回之前的迭代器
        // it++
        self operator++(int)
        {
            // 1. 创建一个名为 tmp 的临时迭代器对象，它通过调用 __list_iterator 的拷贝构造函数，用当前迭代器 *this 进行初始化。
            self tmp(*this); // 创建一个临时迭代器对象，保存当前迭代器的状态
            // 2. 将当前迭代器移动到下一个节点
            _node = _node->_next;
            // 3. 返回之前的迭代器状态
            return *this;
        }
        // 后置++为什么有(int)？？？
        // 后置++运算符重载接受一个额外的 int 参数（这里没有实际使用它，只是为了区分前置和后置++），并返回一个值而不是引用。
        // C++中的后置++运算符必须在参数列表中声明一个int类型的参数，以便与前置++运算符进行区分。这种参数实际上并没有用处，只是为了在编译器中区分前置和后置++运算符的不同。没有参数的后置++运算符将会与前置++运算符具有相同的参数列表，这会导致编译器无法正确区分它们，从而导致编译错误。

        self &operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        self operator--(int)
        {
            self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

        // 这个重载函数的目的是允许通过迭代器访问当前节点的数据。
        // Ref：表示解引用运算符返回的类型。
        //
        Ref operator*()
        {
            return _node->_data; // 是指向当前节点存储数据的成员变量 _data。通过返回 _data 的引用，允许用户通过迭代器解引用（使用 *it）来访问和修改节点中存储的数据。
        }

        // 有点难理解
        // Ptr：表示指针访问运算符返回的类型。
        // 返回节点数据的地址
        Ptr operator->()
        {
            return &_node->_data;
        }

        // 上面俩的解释：
        // 对于普通迭代器，Ref 是 T& ，所以 operator*() 返回节点数据的引用，允许修改数据。
        // 对于常量迭代器，Ref 是 const T& ，所以 operator*() 返回节点数据的常量引用，不允许修改数据。

        // 对于普通迭代器，Ptr 是 T* ，所以 operator->() 返回指向节点数据的指针，允许通过指针修改数据。
        // 对于常量迭代器，Ptr 是 const T* ，所以 operator->() 返回指向节点数据的常量指针，不允许通过指针修改数据。

        bool operator!=(const self &s)
        { //_node 是指向当前节点的指针，比较 _node 和 s._node 是否相等，如果不相等返回 true，否则返回 false。
            return _node != s._node;
        }

        bool operator==(const self &s)
        { // s是另一个迭代器对象,
            return _node == s._node;
        }

        // 迭代器为什么不提供析构函数
    };

    template <class T>
    class list
    {

    public:
        typedef ListNode<T> Node;
        /*typedef __list_iterator<T> iterator;*/
        typedef __list_iterator<T, T &, T *> iterator;                   // 定义普通迭代器
        typedef __list_iterator<T, const T &, const T *> const_iterator; // 定义常量迭代器
        // 这样，iterator 和 const_iterator 都使用同一个 __list_iterator 结构体模板，只是通过不同的模板参数实例化，分别实现普通迭代器和常量迭代器的功能。
        // 第一个 三个参数 T,Ref，Ptr分别就是，T,T&,T*.
        // 第二个 三个参数 T,Ref，Ptr分别就是  T,const T&,const T*

        // 反向迭代器
        // typedef ReverseListIterator<iterator> reverse_iterator;
        // typedef ReverseListIterator<const_iterator> const_reverse_iterator;

        // 访问
        iterator begin()
        {
            // return iterator(_head->_next);  下面这个也可以，因为可以简单点写，因为隐式类型转换， 迭代器是单参数的构造函数？？？
            return _head->_next;
        }

        iterator end()
        {
            return _head;
            // 对于带头节点的双向循环链表，_head 节点实际上是链表的“尾部”。因为链表的最后一个有效节点的下一个节点是 _head，所以返回 _head 可以表示链表的末尾位置。
        }

        /*return _head->_next 和 return iterator(_head->_next) 在某些情况下可以看起来是一样的，但它们的行为是不同的，具体取决于上下文和类型的隐式转换。

        1. return _head->_next
        假设 _head->_next 是一个 Node * 类型的指针。如果 iterator 类型的构造函数接受 Node * 类型的参数，并且在返回时能够自动转换，那么 return _head->_next 可以看起来像是在返回一个 iterator 对象。实际上，如果 iterator 的构造函数接受 Node * ，_head->_next 会通过这个构造函数隐式地转换为 iterator 类型。

        2. return iterator(_head->_next)
        这是一个显式的构造函数调用，它直接创建一个 iterator 对象，使用 Node * 参数 _head->_next 来初始化它。这里明确地调用了 iterator 的构造函数来创建一个新的 iterator 实例。*/

        const_iterator begin() const
        {
            return _head->_next;
        }

        const_iterator end() const
        {
            return _head;
        }

        void empty_init()
        {
            // 用于创建一个新的链表节点对象，并将 _head 指针指向这个新创建的节点。
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }

        // 构造函数
        list()
        {
            empty_init();
        }

        list(size_t n, const T &val = T())
        {
            empty_init();
            for (size_t i = 0; i < n; i++)
            {
                push_back(val);
            }
        }
        list(int n, const T &val = T())
        {
            empty_init();
            for (size_t i = 0; i < n; i++)
            {
                push_back(val);
            }
        }

        template <class InputIterator>
        list(InputIterator first, InputIterator last)
        {
            empty_init();
            while (first != last)
            {
                push_back(*first);
                first++;
            }
        }

        list(initializer_list<T> ilt)
        {
            // 使用初始化列表的迭代器进行遍历，从头到尾一个一个元素地插入到列表中。
            // push_back 函数会将元素添加到列表的末尾。
            empty_init();
            initializer_list<T>::iterator it = ilt.begin();
            while (it != ilt.end())
            {
                push_back(*it); // 复用 push_back 函数
                it++;
            }
        }
        list(initializer_list<T> ilt)
        {
            empty_init();
            for (auto &e : ilt)
            {
                push_back(e);
            }
            // 使用范围 for 循环遍历初始化列表中的所有元素，
            // 并使用 push_back 函数将每个元素添加到列表的末尾。这种方式比迭代器遍历更加简洁和易读。
        }

        list(initializer_list<T> ilt)
        {
            empty_init();
            list<T> tmp(ilt.begin(), ilt.end()); // 复用迭代器初始化的函数，构造出临时对象
            std::swap(_head, tmp._head);         // 交换哨兵位节点指针
        }

        // 拷贝构造(深拷贝)   一个节点一个节点的拷贝
        list(list<T> &lt)
        {
            empty_init();
            for (const auto &e : lt)
            {
                push_back(e);
            }
        }
        // 深拷贝的关键步骤：
        //	节点复制：
        // 每次调用 push_back(e) 时，都创建一个新的 ListNode 对象，并将 e 的值复制到新节点的 data 成员中。

        // 拷贝构造 - 现代写法
        // lt2(lt1)
        // list(const list<T>& lt) {
        //	empty_init();
        //	list<T> tmp(lt.begin(), lt.end()); // 迭代器区间构造
        //	std::swap(_head, tmp._head); // 交换哨兵位指针
        //}

        // 拷贝构造函数，接受一个常量引用链表对象作为参数
        // list(const list<T>& lt)
        //{
        //	// 初始化新链表为空链表
        //	empty_init();

        //	// 获取给定链表的第一个节点的迭代器
        //	const_iterator it = lt.begin();

        //	// 遍历给定链表的所有节点
        //	while (it != lt.end())
        //	{
        //		// 将节点的数据插入到新链表的末尾
        //		//这里的end和lt.end()不一样
        //		insert(end(), *it);
        //		// 移动到下一个节点
        //		++it;
        //	}
        //}

        // list(list<T>& lt) 是一个非常规的构造函数，接受一个非常量引用的链表对象。这样可以在需要对传入的链表进行修改的情况下使用。
        // list(const list<T>& lt) 是一个标准的拷贝构造函数，接受一个常量引用的链表对象。这样可以确保不会对传入的链表进行修改。

        // 赋值运算符（普通写法）
        //  lt1=lt2
        list<T> &operator=(list<T> &lt)
        {
            if (this != &lt)
            {
                clear();                 // 先让lt1清空
                for (const auto &e : lt) // 再让lt2的数据尾插到lt1中
                {
                    push_back(e);
                }
            }
        }
        // 为什么返回类型是 list <T>&的引用？？？
        //		链式调用
        //			返回对当前对象的引用（* this），可以实现链式调用。链式调用允许多个赋值操作连在一起写。例如：
        //			list<int> lt1;
        //			list<int> lt2;
        //			list<int> lt3;
        //			lt1 = lt2 = lt3;
        //			在上面的代码中，lt2 = lt3 返回的是 lt2 的引用，接着 lt1 = lt2 也可以正常工作。这种方式使得代码更简洁和直观。
        //		提高代码效率
        //			返回引用避免了不必要的对象拷贝。在赋值运算符函数中，返回 * this 的引用，而不是返回一个新的对象，可以减少对象拷贝，提升代码的性能和效率。
        //		符合 C++ 的惯例
        //			在 C++ 中，赋值运算符通常返回左值引用，以符合语言习惯和标准库的设计。这样做使得自定义类型的行为与内置类型一致，从而提高代码的可读性和可维护性。

        // 赋值运算符（现代写法）
        // list& operator=(list lt)   // （也可以不写模板参数）也可以这样写，但仅限在类里面， 类型的时候就不行

        void swap(list<T> &tmp)
        {
            std::swap(_head, tmp._head);
        }
        list<T> operator=(list<T> lt) // 不能用引用
        {
            swap(lt);
            return *this;
        }

        void clear()
        {
            // 检查链表是否为空，如果为空则直接返回
            if (begin() == end())
            {
                return;
            }
            // begin() 和 end() 方法是属于包含这些方法的类的成员函数，它们在不传递参数的情况下会被假定为作用于当前对象（即 this 指针指向的对象）。
            iterator it = begin();
            while (it != end())
            {
                // 调用 erase 方法并将 it 更新为被删除节点的下一个节点
                it = erase(it);
                // erase 会返回被删除节点的下一个节点
            }

            // 哨兵节点重新指向自己，确保后续插入操作不会出错
            _head->_prev = _head;
            _head->_next = _head;
        }

        // erase 会有迭代器失效问题

        // 析构函数
        // 注意析构需要把带哨兵位的头结点也要去掉.和清空不一样
        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

        void pop_front()
        {
            // erase(_head->_next);
            erase(begin());
        }
        void pop_back()
        {
            // erase(_head->_prev);
            erase(--end());
        }
        // 为何用--end()？？？
        // end() 函数：
        //	end() 函数返回的是指向链表结尾的迭代器，通常是指向哨兵节点（尾后节点）的迭代器。
        //--end() 操作：
        //	end() 返回的迭代器通常指向链表的尾后位置，即哨兵节点的位置。--end() 操作将这个迭代器前移一个位置，指向链表中最后一个实际节点的位置。

        void push_front(const T &x)
        {
            insert(begin(), x);
        }

        void push_back(const T &x)
        {
            // insert(end(), x);  //复用insert的版本

            // 画图看就比较清晰了
            Node *newnode = new Node(x);
            Node *tail = _head->_prev; // head的前一个节点是尾节点，下一个节点是头结点

            tail->_next = newnode;
            newnode->_prev = tail;
            newnode->_next = _head;
            _head->_prev = newnode;
        }

        // vector insert会导致迭代器失效
        // list会不会？不会
        iterator insert(iterator pos, const T &x) // 返回：  可以简单点写，因为隐式类型转换， 迭代器是单参数的构造函数
                                                  // push_back 就可以复用insert了
        {
            Node *cur = pos._node;
            Node *prev = cur->_prev;
            Node *newnode = new Node(x);

            // head------>prev---->cur--->node1--->node2   向右是next 向左是prev
            //                newnode
            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;

            // return interator(newnode); 也可以 ，为什么？？？
            return newnode;
        }
        iterator erase(iterator pos)
        {
            Node *cur = pos._node;
            //. 用于对象，而 -> 用于指针。
            // pos 是一个迭代器对象，它不是指针。因此我们使用 . 操作符来访问迭代器对象的成员变量 _node。
            Node *prev = cur->_prev;
            Node *next = cur->_next;
            prev->_next = next;
            next->_prev = prev;
            delete cur;
            return next;
        }
        // 补充
        size_t size()
        {
            // 遍历统计
            size_t sz = 0;
            iterator it = begin();
            while (it != end())
            {
                ++sz;
                ++it;
            }
            return sz;
        }
        void resize(size_t n, const T &val = T())
        {
            // 新大小大于当前大小，添加新节点
            if (n > size())
            {
                for (size_t i = size(); i < n; i++)
                {
                    push_back(val);
                }
            }
            // 新大小小于当前大小，删除多余的节点
            else if (n < size())
            {
                iterator it = begin();
                size_t pos = 0;
                // 遍历到需要删除的位置
                while (pos < n && it != end())
                {
                    ++it;
                    ++pos;
                }
                // 从当前位置删除到链表末尾
                while (it != end())
                {
                    it = erase(it);
                }
            }
        }

    private:
        Node *_head;
        // ，__list_iterator 结构体模板内的 typedef 定义了一些别名（alias），这些别名在 list 结构体模板中得以继续使用是因为它们是 __list_iterator 类型的一部分。当 list 使用 __list_iterator 时，这些别名也随之可用
    };

    // 这种情况下就需要const迭代器，这是很常见的现象。
    // const迭代器：自己可以修改所以不是const对象（需要it++）
    // 指向的内容不能修改
    void print_list(const list<int> &lt)
    {
        list<int>::const_iterator it = lt.begin();
        while (it != lt.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }
    void test_list1()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);

        list<int>::iterator it = lt.begin();
        while (it != lt.end())
        {
            *it += 3;
            cout << *it << " ";
            ++it;
        }
        cout << endl;

        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl;
    }

    void test_list2()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);

        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl;
        // 1 2 3 4

        lt.pop_back();
        lt.pop_front();

        lt.push_front(99);
        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl;
        // 2 3 99

        lt.clear();
        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl;
    }

    void test_list3()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        list<int>::iterator it = lt.begin();
        lt.insert(it, 985);
        // 插入完后it仍然指向1

        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl; // 985 1 2 3 4

        ++it;
        // it指向2,在2前插入211
        lt.insert(it, 211);

        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl; // 985 1 211 2 3 4
    }

    void test_list4()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        list<int>::iterator it = lt.begin();
        it = lt.insert(it, 985);
        // 因为it返回的是新插入的节点的迭代器，所以it指向第一个元素985

        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl; // 985 1 2 3 4

        ++it;
        // it指向1,在1前插入211
        lt.insert(it, 211); // it仍然指向1
        // it=lt.insert(it, 211); //it指向211
        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl; // 985 1 211 2 3 4
    }

    // 讲解拷贝构造
    // 默认的浅拷贝 会析构两次 出现问题
    void test_list5()
    {
        // list<int> lt;
        // lt.push_back(1);
        // lt.push_back(2);
        // lt.push_back(3);
        // lt.push_back(4);
        ////list<int> copy(lt);
        // for (auto e : copy)
        //{
        //	cout << e << " ";
        // }
    }

    void test_list6()
    {
    }

}